package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description: 跳跃游戏 II
 * 45 jump-game-ii
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * <p>
 * 假设你总是可以到达数组的最后一个位置。
 * <p>
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class JumpGameIi {

    public static void main(String[] args) {
//        int[] nums = {1, 2};
//        int[] nums = {2, 3, 1, 1, 4};
        int[] nums = {2,3,1,1,1,2,1,3,3,4};
        Solution solution = new JumpGameIi().new Solution();
        System.out.println(solution.jump(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 贪心算法，是个思想，很有意思的思想
         * 怎么感觉更像动态规划呢
         *
         * @param nums
         * @return
         */
        public int jump(int[] nums) {
            if(nums.length <= 1){
                return 0;
            }
            int length = nums.length;
            int count = 0;
            int i = 0;
            while (i < length) {

                int jump = nums[i] + i;

                if(jump >= length - 1){
                    return ++count;
                }


                int max = 0;
                int tempI = i + 1;
                i = jump;

                while (tempI <= jump) {
                    int sub = nums[tempI] + tempI - jump;
                    if(sub >= max){
                        max = sub;
                        i = tempI;
                    }
                    tempI++;
                }
                count++;

            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
